/**
 * 718.最长重复子数组
 */
public class Exerciser8 {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // dp[i][j]: nums1中以 i 位置为结尾的所有子数组中 和 nums2中以 j 位置为结尾的所有子数组中，公共的、长度最长的子数组的长度
        int[][] dp = new int[m + 1][n + 1];
        // 初始化，因为新加的节点的行和列均代表某一个数组为空，那么 公共的、长度最长的子数组的长度 为0
        int ret = 0;
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                // 因为 子数组是连续的，如果 n1[i] != n2[j] 的话，那么说明以i和j为结尾的子数组是没有 公共的、长度最长的子数组的长度 的
                if(nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = Math.max(dp[i][j],ret);
                }
            }
        }
        return ret;
    }
}
